package dp;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 464. 我能赢吗
 */
public class P464 {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal == 0) {
            return true;
        }
        Map<Integer, int[]> map = new HashMap<>();
        bt(maxChoosableInteger, desiredTotal, new ArrayList<>(), map);
        for (Map.Entry entry : map.entrySet()) {
            int[] value = (int[]) entry.getValue();
            if (value[0] == 1 && value[1] == 0) {
                return true;
            }
        }
        return false;
    }

    private void bt(int end, int total, List<Integer> savedList, Map<Integer, int[]> map) {
        if (savedList.size() == end || total <= 0) {
            int i = savedList.size() % 2;
            int key = savedList.get(0);
            if (!map.containsKey(key)) {
                map.put(key, new int[]{0, 0});
            }
            if (i == 0) {
                map.get(key)[1] = 1;
            } else {
                map.get(key)[0] = 1;
            }
        } else {
            for (int i = 1; i <= end; i++) {
                if (!savedList.contains(i)) {
                    savedList.add(i);
                    bt(end, total - i, savedList, map);
                    savedList.remove(savedList.size() - 1);
                }
            }
        }
    }

    public boolean dp(int maxChoosableInteger, int desiredTotal) {


        return true;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        boolean flag = new P464().canIWin(18, 79);
        System.out.println("use" + (System.currentTimeMillis() - start));
        System.out.println(flag);
    }
}
